package leetcode.d_1_99;

import java.util.LinkedList;
import java.util.List;

// https://leetcode.cn/problems/word-search/
// 单词搜索
public class P79 {
    public static void main(String[] args) {
        P79 test = new P79();
        char[][] board = new char[][]{{'A','B','C','E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
        System.out.println(test.exist(board, "ABCB")); // false
        System.out.println(test.exist(board, "ABCCED")); // true
    }

    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        boolean[][] used = new boolean[m][n]; // 避免走回头路
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (dfs(board, word, i, j, 0, used)) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean dfs(char[][] board, String word, int i, int j, int idx, boolean[][] used) {
        if (idx == word.length()) {
            return true;
        }
        if (i < 0 || i>=board.length) {
            return false;
        }
        if (j < 0 || j>=board[0].length) {
            return false;
        }
        if (used[i][j]) {
            return false;
        }
        if (board[i][j] != word.charAt(idx)) {
            return false;
        }
        used[i][j] = true;
        boolean res1 = dfs(board, word, i-1, j, idx+1, used);
        boolean res2 = dfs(board, word, i+1, j, idx+1, used);
        boolean res3 = dfs(board, word, i, j-1, idx+1, used);
        boolean res4 = dfs(board, word, i, j+1, idx+1, used);
        if (res1 || res2 || res3 || res4) {
            return true;
        }
        used[i][j] = false;
        return false;
    }
}
